// 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

// 示例:

// 输入: [-2,1,-3,4,-1,2,1,-5,4],
// 输出: 6
// 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 进阶:

// 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

#include <vector>
#include <algorithm>

using namespace std;

class Solution1 {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int cur{0}; // 以当前数字结束的最大子序和
        for (int num : nums) {
            cur = max(cur + num, num);
            res = max(res, cur);
        }
        return res;
    }
};

// 分治法，二分搜索
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        return func(nums, 0, n-1);
    }
    int func(vector<int>& nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int l_max = func(nums, left, mid-1);
        int r_max = func(nums, mid+1, right);
        int m_max = nums[mid];
        int t = m_max;
        for (int i = mid-1; i >= left; --i) {
            t += nums[i];
            m_max = max(m_max, t);
        }
        t = m_max;
        for (int i = mid+1; i <= right; ++i) {
            t += nums[i];
            m_max = max(m_max, t);
        }
        return max(m_max, max(l_max, r_max));
    }
};